package com.kevin.Code.Tree;

/**
 * @author Vinlee Xiao
 * @Classname ConvertSortedArrayToBinarySearchTree
 * @Description Leetcode 108. 将有序数组转换为二叉搜索树 中等难度
 * @Date 2021/12/16 20:58
 * @Version 1.0
 */
public class ConvertSortedArrayToBinarySearchTree {

    /**
     * 难点是怎么保持平衡二叉搜索树
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode node = dfs(nums, 0, nums.length - 1);
        return node;
    }


    /**
     * @param nums
     * @return
     */
    private TreeNode dfs(int[] nums, int leftIndex, int rightIndex) {
        //如果当前右指标小于左指标则直接返回null
        if (leftIndex > rightIndex) {
            return null;
        }

        if (leftIndex == rightIndex) {
            return new TreeNode(nums[leftIndex]);
        }

        int mid = (leftIndex + rightIndex) / 2;
        TreeNode node = new TreeNode(nums[mid]);

        TreeNode leftNode = dfs(nums, leftIndex, mid - 1);

        TreeNode rightNode = dfs(nums, mid + 1, rightIndex);
        node.left = leftNode;
        node.right = rightNode;

        return node;
    }

    private void printTreeByInorder(TreeNode root) {
        if (root == null) {
            return;
        }
        printTreeByInorder(root.left);
        System.out.print(root.val + " ");
        printTreeByInorder(root.right);

    }


    public static void main(String[] args) {

        int[] nums = new int[]{-10, -3, 0, 5, 9};
        ConvertSortedArrayToBinarySearchTree c = new ConvertSortedArrayToBinarySearchTree();
        TreeNode node = c.sortedArrayToBST(nums);

        c.printTreeByInorder(node);
    }
}
